package com.le.basic.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 *  实现二叉树的先序、中序、后序遍历，包括递归方式和非递归 方式
 */
public class Code_01_PreInPosTraversal {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 递归先序遍历
     * @param head
     */
    public static void preOrderRecur(Node head){
        if (head == null){
            return;
        }
        System.out.print(head.value + "  ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    /**
     * 递归中序遍历
     * @param head
     */
    public static void inOrderRecur(Node head){
        if (head == null){
            return;
        }
        inOrderRecur(head.left);
        System.out.print(head.value + "  ");
        inOrderRecur(head.right);
    }

    /**
     * 递归中序遍历
     * @param head
     */
    public static void postOrderRecur(Node head){
        if (head == null){
            return;
        }
        postOrderRecur(head.left);
        postOrderRecur(head.right);
        System.out.print(head.value + "  ");
    }

    /**
     * 先序非递归
     * @param head
     */
    public static void preOrderUnRecur(Node head){
        if (head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        if (head != null){
            stack.push(head);
            while (!stack.isEmpty()){
                head = stack.pop();
                System.out.print(head.value + "  ");
                if (head.right != null){
                    stack.push(head.right);
                }
                if (head.left != null){
                    stack.push(head.left);
                }
            }
        }
    }

    /**
     * 中序非递归
     * @param head
     */
    public static void inOrderUnRecur(Node head){
        if (head == null){
            return;
        }
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || head != null){
            if (head != null){
                stack.push(head);
                head = head.left;
            }else {
                head = stack.pop();
                System.out.print(head.value + "  ");
                head = head.right;
            }
        }
    }

    /**
     * 后序非递归
     * @param head
     */
    public static void postOrderUnRecur(Node head){
        if (head == null){
            return;
        }
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.isEmpty()){
            head = stack1.pop();
            stack2.push(head);
            if (head.left != null){
                stack1.push(head.left);
            }
            if (head.right != null){
                stack1.push(head.right);
            }
        }
        while (!stack2.isEmpty()){
            System.out.print(stack2.pop().value + "  ");
        }

    }

    /**
     * 按层打印
     * @param head
     */
    public static void printLevel(Node head){
        if (head == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()){
            head = queue.poll();
            System.out.println(head.value);
            if (head.left != null){
                queue.offer(head.left);
            }
            if (head.right != null){
                queue.offer(head.right);
            }
        }
    }


    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);
        Node head1 = head;
        Node head2 = head;
        Node head3 = head;
//        System.out.println("preOrderRecur---");
//        preOrderRecur(head1); //5  3  2  1  4  8  7  6  10  9  11
//        System.out.println();
//        preOrderUnRecur(head1);
//        System.out.println();
//        System.out.println("inOrderRecur---");
//        inOrderRecur(head2);//1  2  3  4  5  6  7  8  9  10  11
//        System.out.println();
//        inOrderUnRecur(head2);
//        System.out.println();
//        System.out.println("postOrderRecur---");
//        postOrderRecur(head3);//1  2  4  3  6  7  9  11  10  8  5
//        postOrderUnRecur(head);
        printLevel(head);
    }
}
